/**
 * 二进制手表
 * 二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。
 * 每个 LED 代表一个 0 或 1，最低位在右侧。
 * 给你一个整数 turnedOn ，表示当前亮着的 LED 的数量，返回二进制手表可以表示的所有可能时间。你可以 按任意顺序 返回答案。
 * tips：小时不会以零开头；分钟必须由两位数组成，可能会以零开头。
 **/
#include<iostream>
#include<vector>
#include<string>
using namespace std;

/**
 * 因为 0 <= turnedOn <= 10，小时[0,11],分钟[0,59],数据量不大，可以枚举
 * Solution 1:枚举时分，反向思考，求出每个时刻的二进制表达有几个1，用结果和turnedOn匹配
 * 而不是从turnedOn找时间的1位
 **/
class Solution {
public:
    vector<string> readBinaryWatch(int turnedOn) {
        vector<string> result;
        for(int h=0; h<12; h++){
            for(int m=0; m<60; m++){
                //__builtin_popcount()用于计算一个 32 位无符号整数有多少个位为1
                if(__builtin_popcount(h) + __builtin_popcount(m) == turnedOn){
                    result.push_back(to_string(h) + ":" + (m < 10 ? "0":"") + to_string(m));
                }
            }
        }
        return result;
    }
};